package ebook.datastructure.typed.chapter7;

import Algorithms.classic.SortUtils;

import java.util.Arrays;

/**
 * description: <br>
 * createTime: 2018/11/711:03 <br>
 *
 * @author zzh
 */
public class Partition {
    public static int partitionIt(int[] array, int pivot) {
        return partitionIt(array, 0, array.length - 1, pivot);
    }

    public static int partitionIt(int[] array, int leftIndex, int rightIndex, int pivot) {
        int left = leftIndex - 1;
        int right = rightIndex + 1;
        while(true) {
            while(left < array.length - 1 && array[++left] <= pivot) {
                ;
            }
            while(right > 0 && array[--right] >= pivot) {
                ;
            }
            if(left >= right) {
                return left;
            }
            swap(array, left, right);
        }
    }


    public static void swap(int[] array, int leftIndex, int rightIndex) {
        int temp = array[leftIndex];
        array[leftIndex] = array[rightIndex];
        array[rightIndex] = temp;
    }

    public static void main(String[] args) {
        int qivot = 50;
        for (int i = 0; i < 10000; i++) {
            int[] array = SortUtils.createRandomArray(10, 100);
            int mid = partitionIt(array, 50);
            for (int j = 0; j < 10; j++) {
                if((j < mid && array[j] > qivot) || (j > mid && array[j] < qivot)) {
                    System.out.println(mid + "\t\t" + Arrays.toString(array));
                }
            }
        }
        System.out.println("over");

    }
}
